package solution.s_106;

import java.util.Arrays;

/**
 * 后序遍历的最后一个元素便是根元素，获取到根元素，从中序遍历将序列分为了两个序列。
 * 然后依次对两个序列执行上面的操作。
 *
 * 比如 中序：[9,3,15,20,7]，后序：[9,15,7,20,3]
 * 3 便是根元素，所以 [9] 便是左子树，[15,20,7] 便是右子树。
 * 再依次对 [9] 和 [15,20,7] 分别进行分析。
 */
public class Solution20200927 {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length <= 0 || postorder.length <= 0) {
            return null;
        }

        return buildTree2(inorder, postorder);
    }

    private TreeNode buildTree2(int[] inOrder, int[] postOrder) {
        int lastIndex = postOrder.length - 1;
        int rootVal = postOrder[lastIndex];
        int rootIndex = getIndex(inOrder, rootVal);

        TreeNode rootNode = new TreeNode(rootVal);

        if (0 < rootIndex) {
            rootNode.left = buildTree2(Arrays.copyOfRange(inOrder, 0, rootIndex), Arrays.copyOfRange(postOrder, 0, rootIndex));
        }

        if (rootIndex < lastIndex) {
            rootNode.right = buildTree2(Arrays.copyOfRange(inOrder, rootIndex+1, lastIndex+1), Arrays.copyOfRange(postOrder, rootIndex, lastIndex));
        }

        return rootNode;
    }

    /**
     * 辅助函数，从中序遍历中返回值所在的位置
     */
    private int getIndex(int[] inorder, int value) {
        for (int i = 0; i < inorder.length; i ++) {
            if (value == inorder[i]) {
                return i;
            }
        }
        return -1;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
